package lc.二叉树.剑指Offer;

import utils.TreeNode;

import java.util.HashMap;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/31
 */
public class 剑指Offer07_重建二叉树 {
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return recur(0,0, inorder.length - 1);


    }

    private TreeNode recur(int root, int left, int right) {

        if (left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        Integer i = map.get(preorder[root]);
        //左子树的根的索引为先序中的根节点+1
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        node.left = recur(root + 1,left,i - 1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的右边界为中序中原来右子树的边界
        node.right = recur(root + (i - left) + 1,i+1,right);
        return node;
    }
}
